Dr. J's Maths.com
Where the techniques of Maths
are explained in simple terms.

Network analysis & Graph Theory.
Summary of steps for applying Dijkstra's algorithm.


 

Dijkstra's algorithm finds the shortest path through a network.

The steps to follow to find the shortest path between vertex A and vertex F are summarised below.

 

Step 1: Write out the vertices in a row - starting with the starting vertex (A) and ending with the finishing vertex (F).
  A B C D E F
             
Step 2: Write the letter for the start in a column starting before row 1.
  A B C D E F
A            
Step 3: Record in the first row of the table the distances from A to B and from A to D because they represent a step of 1 from vertex A.
  A B C D E F
A   3   5    
Step 4: Select the vertex with the minimum distance - here B has 3 - and then write B in the next row below A with the distance from A in brackets.
  A B C D E F
A   3   5    
B (3)            
Step 5: Add the value you wrote after the B to each of the distances to the vertices linked to B and record these in the same row in the appropriate column. For example B to C is 9 so add that to the 3 in brackets after B.
  A B C D E F
A   3   5    
B (3)     12 10 11  
Step 6:

Check each column to determine if the
new number is less than those above it.

ABD = 10 but A direct to D was 5 - so discard the 10. A to D is shortest so include D in the first column of the next row.
  A B C D E F
A   3   5    
B (3)     12 10 11  
D (5)         12  
Step 7: The distance A to D to E (5 + 7=12) is larger than the distance A to B to E (3+8=11) so discard DE.
The next shortest distance is from B to E. Write E in the first column with its distance (11).
  A B C D E F
A   3   5    
B (3)     12 10 11  
D (5)         12  
E (11)            
Step 8: We can’t go backwards from E so the only vertex remaining is F. Add to weight to E (=11) to the EF weight to obtain the total weight.
  A B C D E F
A   3   5    
B (3)     9 7 8  
E (11)           17
 

So the shortest path from A to F is:

A B E F and its length is 17 (11 + 6).